package main

import (
	"container/heap"
	"fmt"
)

// 有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。请进行优化。
// 2021.7.31  11:30    TaskA
// 2021.8.1   1:20     TaskB
// 2021.8.1   1:21     TaskC
// 2021.8.1   23:23    TaskD
// 如上所述，这样每隔 1 秒就去扫描的方法比较低效：

// 每个任务的约定执行时间之间可能会隔很久，这样会多出很多无用的扫描。
// 每次都去扫描整个任务列表的话，如果该表比较大，扫描时间间隔又及其短，对性能时间消耗就比较大了。
type Item struct {
	value    string
	priority int
	index    int
}

//优先级队列需要实现heap的interface
type PriorityQueue []*Item

//绑定len方法
func (pq PriorityQueue) Len() int {
	return len(pq)
}

//绑定Less方法，这里用的是小于号，生成的是小根堆
//交换的标准是 优先级
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

//绑定swap方法
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index, pq[j].index = i, j
}

//绑定push方法
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)

	//标记该元素的索引位置
	n := len(*pq)
	item.index = n
	*pq = append(*pq, item)
}

//绑定pop方法，将index置为-1是为了表示该数据已经出了优先级队列了
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	item.index = -1
	return item

}

//更新修改了优先级和值的item在优先级队列中的位置
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

func TestPriorityQueue() {
	//创建节点并设计他们的优先级
	items := map[string]int{"TaskA": 5, "TaskB": 3, "TaskC": 9}
	i := 0
	pq := make(PriorityQueue, len(items))
	for k, v := range items {
		pq[i] = &Item{
			value:    k,
			priority: v,
			index:    i,
		}
		i++
	}
	heap.Init(&pq) //初始化堆
	item := &Item{
		value:    "TaskD",
		priority: 1,
	}
	heap.Push(&pq, item) //入优先级队列
	pq.update(item, item.value, 6)
	for len(pq) > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s index:%.2d\n", item.priority, item.value, item.index)
	}

}
